XJOI200731 题解

数位dp, 模拟赛, 贪心

A

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
/*
我仿佛智障了= =
这一看就很可以递推的样子啊，数位 dp 真的不是很难，是我数位 dp 太弱了
*/
#include <bits/stdc++.h>
#define rep(i, x, y) for (int i = x; i <= y; i++)
using namespace std;

typedef long long ll;
const int mod = 1e9 + 7, N = 1e6 + 10;
ll T, K, l, r, f[2][3][65], bit2[65];
// f[0, ,] 是已经有一位取小、后面就没有限制的方案数
// f[1, ,] 是受/不受到数位限制的总方案数

ll sub(ll a, ll b) { return (a - b + mod) % mod; }
ll add(ll a, ll b) { return (a + b + mod) % mod; }

void init(int n) {
    bit2[0] = 1;
    rep(i, 1, n)
        bit2[i] = bit2[i - 1] * 2 % mod;
    f[0][0][0] = 3;  // 这里的 0 是 (1 << 0)，也就是 1！1 有 3 种方案！！！
    f[0][1][0] = 1;
    f[0][2][0] = 1;
    rep(i, 1, n) {
        f[0][0][i] = (f[0][0][i - 1] + 2 * f[0][0][i - 1]) % mod;
        f[0][1][i] = (f[0][1][i - 1] + 2 * f[0][1][i - 1] % mod + bit2[i] * f[0][0][i - 1] % mod) % mod;
        f[0][2][i] = (f[0][2][i - 1] + 2 * f[0][2][i - 1] % mod + 2 * f[0][1][i - 1] % mod * bit2[i] % mod + bit2[i] * bit2[i] % mod * f[0][0][i - 1] % mod) % mod;
    }
}

ll calc(ll n, int K) {
    if (!n) return 0;  // !!!
    ll cnt = 0, x = n;
    while (x) x >>= 1, ++cnt;
    f[1][0][0] = (n & 1) ? 3 : 1;
    f[1][1][0] = (n & 1) ? 1 : 0;
    f[1][2][0] = (n & 1) ? 1 : 0;
    rep(i, 1, cnt) {
        if ((n >> i) & 1) {
            f[1][0][i] = (f[0][0][i - 1] + 2 * f[1][0][i - 1] % mod) % mod;
            f[1][1][i] = (f[0][1][i - 1] + 2 * f[1][1][i - 1] % mod + bit2[i] * f[1][0][i - 1] % mod) % mod;
            f[1][2][i] = (f[0][2][i - 1] + 2 * f[1][2][i - 1] % mod + 2 * f[1][1][i - 1] % mod * bit2[i] % mod + bit2[i] * bit2[i] % mod * f[1][0][i - 1] % mod) % mod;
        } else {
            rep(j, 0, 2)
                f[1][j][i] = f[1][j][i - 1];
        }
    }
    return f[1][K][cnt];
}

int main() {
    cin >> T >> K;
    init(60);
    while (T--) {
        scanf("%lld%lld", &l, &r);
        printf("%lld\n", sub(calc(r, K), calc(l - 1, K)));
    }
    return 0;
}

B

考虑贪心，不断合并平均值最大的块和它的父亲所在连通块。

证明的话，sum1 num2 < sum2 num1, sum1 / num1 < sum2 / num2，按平均值从大到小排序，堆维护。

进阶版的 poj-2054，很像 AGC023f-01 on tree，经典贪心了。

注意！！！我自己写的时候用了priority_queue，但对 sum 和 num 的操作却是在外面做的，也就是说对pq没有修改！而且这样还破坏了pq的结构！！！最后 WA 成了 15pts！！！痛心

正确的做法是每次将 fa 从堆里弹出来，对 fa 的操作做完后再 push 一个新的 fa 进去。为了方便执行“弹出操作”，我们用 set 维护优先队列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <bits/stdc++.h>
#define rep(i, x, y) for (int i = x; i <= y; i++)
using namespace std;

typedef long long ll;
const int N = 1e5 + 10;
ll n, rt, c[N], fa[N], num[N], sum[N], ans, fat[N];
vector<int> nxt[N];
struct node {
    int id;
    bool operator < (const node &a) const {
        ll t2 = sum[id] * num[a.id], t1 = sum[a.id] * num[id];
        return t1 < t2 || (t1 == t2 && id > a.id);
    }
};
set<node> q;

void dfs(int x, int f) {
    fat[x] = f;
    for (int i = 0; i < nxt[x].size(); i++) {
        int y = nxt[x][i];
        if (y == f) continue;
        dfs(y, x);
    }
}

int getfa(int x) {
    return fa[x] == x ? x : fa[x] = getfa(fa[x]);
}

int main() {
    cin >> n >> rt;
    rep(i, 1, n) {
        scanf("%lld", &sum[i]);
        num[i] = 1;
        fa[i] = i;
    }
    rep(i, 1, n - 1) {
        int x, y; scanf("%d%d", &x, &y);
        nxt[x].push_back(y), nxt[y].push_back(x);
    }
    dfs(rt, rt);
    rep(i, 1, n)
        if (i != rt) q.insert((node){i});
    while (q.size()) {
        int x = q.begin()->id;
        q.erase(q.begin());
        int f = getfa(fat[x]);
        q.erase((node){f});
        ans += sum[x] * num[f];
        sum[f] += sum[x], num[f] += num[x];
        fa[x] = f;
        if (f != rt) q.insert((node){f});
    }
    printf("%lld\n", ans + sum[rt]);
    return 0;
}